package 动态规划;

// 状态：F(i,j)：从(0,0)到达(i,j)的路径个数
// 状态转移方程：F(i,j) = Math.min(F(i,j-1) + F(i-1,j))+array[i][j]
// 初始状态：F(0,0) = array[0][0]
//       第一行：F(0,j) = F(0,j-1)+array[0][j];
//       第一列：F(i,0) = F(i-1,0)+array[i][0];
// 返回结果：F(row-1,col-1)
public class LeetCode64_最小路径和 {
    public int minPathSum(int[][] grid) {
        if(grid.length == 0) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        for (int i = 1; i < col; i++) {
            grid[0][i] = grid[0][i-1] + grid[0][i];
        }
        for (int i = 1; i < row; i++) {
            grid[i][0] = grid[i-1][0] + grid[i][0];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                grid[i][j] = Math.min(grid[i][j-1],grid[i-1][j])+
                        grid[i][j];
            }
        }
        return grid[row-1][col-1];
    }
}
